import java.util.Arrays;

/**
 * 描述:
 * > 算法稳定性:
 * 归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。
 * 在合并的过程中，如果 A[p…q] 和 A[q+1…r] 之间有值相同的元素，那我们可以先把 A[p…q] 中的元素放入 tmp 数组。
 * 这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法
 * > 时间复杂度:
 * 归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
 * > 空间复杂度:
 * 1. 归并排序的时间复杂度任何情况下都是 O(nlog)，看起来非常优秀。
 * (而即便是快速排序，最坏情况下，时间复杂度也是 O(n的2次方))，但是，归并排序并没有像快排那样应用广泛，这是为什么呢？
 * 因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。
 * 2. 这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。
 * 不过，它占用的临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是O(n)。
 */
public class MergeSort {
    public static void main(String[] args) {
        Integer[] array = {9, 6, 3, 2, 5, 5, 1, 7, 8, 2, 4, 3};
        System.out.println("\nmergeSortRes:");
        Integer[] mergeSortRes = mergeSort(array);
        for (int i = 0; i < mergeSortRes.length; i++) {
            System.out.printf(mergeSortRes[i] + ",");
        }
    }

    /**
     * @param array
     * @return
     */
    public static Integer[] mergeSort(Integer[] array) {
        if (array.length < 2) {
            return array;
        }
        int midIndex = array.length / 2;
        // 注意边界index
        // Arrays.copyOfRange(array, 0, 1); 会将数组中[0]元素进行拷贝
        // Arrays.copyOfRange(array, 1, 3); 会将数组中[1]、[2]元素进行拷贝
        Integer[] left = Arrays.copyOfRange(array, 0, midIndex);
        Integer[] right = Arrays.copyOfRange(array, midIndex, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * merge 合并算法非常有意思，也是要重点关注的
     * @param left
     * @param right
     * @return
     */
    public static Integer[] merge(Integer[] left, Integer[] right) {
        // 需要借助临时空间存储即将合并的数据
        Integer[] result = new Integer[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else {
                result[index] = left[i++];
            }
        }
        return result;
    }
}
